/* display.c */

/* debug start */
#ifdef DEBUG 

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

#define BUFFSIZE 512
#define PAGECOUNT 64
#define ERR_MEMA "Memory Allocation Error\n"
#define WORDFIELDLENGTH 15
#define SPACEFIELDLENGTH 2
#define PAGEFIELDLENGTH 63

/* global var */
char rbuf[BUFFSIZE];
char firstletter[1];

typedef struct plist{
	struct plist *nextp;
	int pnum;
}plist_t;

typedef struct wlist{
	struct wlist *up;
	struct wlist *leftp;
	struct wlist *rightp;
	char *wordp;
	plist_t *top;
	plist_t *lastp;
}wlist_t;

wlist_t *wtop = (wlist_t *)NULL;
/* functions */
void register_word(int npage, char *wordp);
plist_t * allocp(void);
wlist_t * allocw(void);
void display(wlist_t *wlp);
void print_word(wlist_t *wlp);
void print_plist(plist_t *plp);
void print_firstletter(char ch);
void padding_space(int num);

/* test display */
main(){
	//register word
	register_word(3, "test");
	register_word(4, "test");
	register_word(4, "apple");
	register_word(7, "fukuda");
	register_word(9, "chou");
	register_word(99, "teki");
	register_word(583, "tanaka");
	register_word(383, "koyama");
	//call display() 
	display(wtop);

	return EXIT_SUCCESS;

}
/* function */
void register_word(int npage, char *wordp){

   plist_t *plp;
   wlist_t *wlp;

   int wcomp;

   wlist_t *wlorgp;

   if(wtop == (wlist_t *)NULL){
      plp = (plist_t *)malloc(sizeof(plist_t));
      if( plp == (plist_t *)NULL){
         printf(ERR_MEMA);
         exit(1);
      }
      plp->nextp = (plist_t *)NULL;
      plp->pnum = npage;
      wlp = (wlist_t *)malloc(sizeof(wlist_t));
      if(wlp == (wlist_t *)NULL){
         free(plp);
         printf(ERR_MEMA);
         exit(1);
      }
      wlp->up = (wlist_t *)NULL;
      wlp->leftp = (wlist_t *)NULL;
      wlp->rightp = (wlist_t *)NULL;
      wlp->wordp = wordp;
      wlp->top = plp;
      wlp->lastp = plp;

      wtop = wlp;

   }else{
      wlorgp = wtop;
      while(wlorgp != (wlist_t *)NULL){
         wcomp = strcmp(wordp, wlorgp->wordp);
         if(wcomp < 0){
            if(wlorgp->leftp == (wlist_t *)NULL){
               plp = allocp();
               wlp = allocw();
               wlp->top = plp;
               wlp->lastp = plp;
               wlp->wordp = wordp;
               plp->pnum = npage;
               wlorgp->leftp = wlp;
               wlp->up = wlorgp;
               return;
            }else{
               wlorgp = wlorgp->leftp;
            }
         }else if(wcomp > 0){
            if(wlorgp->rightp == (wlist_t *)NULL){
               plp = allocp();
               wlp = allocw();
               wlp->top = plp;
               wlp->lastp = plp;
               wlp->wordp = wordp;
               plp->pnum = npage;
               wlorgp->rightp = wlp;
               wlp->up = wlorgp;
               return;
            }else{
               wlorgp = wlorgp->rightp;
            }
         }else{ 
            if(wlorgp->lastp->pnum == npage){
               free(wordp);
               return;
            }else{
               plp = allocp();
               plp->pnum = npage;
               wlorgp->lastp->nextp = plp;
               wlorgp->lastp = plp;
               return;
            }
         }
      }
   }
}


plist_t *allocp(void){
	plist_t *plp;
	
	plp = (plist_t *)malloc(sizeof(plist_t));
	if(plp == (plist_t *)NULL){
		printf(ERR_MEMA);
		return ((plist_t *)NULL);
	}
	plp->nextp = (plist_t *)NULL;
	plp->pnum = 0;

	return (plp);

}

wlist_t *allocw(void){
	wlist_t *wlp;
	wlp = (wlist_t *)malloc(sizeof(wlist_t));
	if(wlp == (wlist_t *)NULL){
		printf(ERR_MEMA);
		return ((wlist_t *)NULL);
	}
	wlp->up = (wlist_t *)NULL;
	wlp->rightp = (wlist_t *)NULL;
	wlp->leftp = (wlist_t *)NULL;

	return (wlp);
}

/* debug end */
#else

#include "common.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

#endif

char outputbuf[WORDFIELDLENGTH + SPACEFIELDLENGTH + PAGEFIELDLENGTH];

/* 最初の1文字を出力する
*args 
* ch 最初の1文字
*Return Value
* なし
*/
void print_firstletter(char ch){
	int idx;
	for(idx=0; idx<WORDFIELDLENGTH; idx++){/* 単語フィールドには'#' */
		putc('#', stdout);
	}
	printf(" %c ", ch);
	for(idx=0; idx<PAGEFIELDLENGTH; idx++){/* ページフィールドには'#' */
		putc('#', stdout);
	}
	putc('\n', stdout);
}
/* 単語とその掲載ページを出力する
*args 
* wlp 単語リストへのポインタ
*Return Value
* なし
*/
void display(wlist_t *wlp){
	char buff[BUFFSIZE];
	
	memset(buff, '\0', BUFFSIZE);
	

	if(wlp != NULL){/* 全ての単語を表示するまでループ */
		/* 左の子ノードを表示 */ 
		display(wlp->leftp); 
		
		strncpy(buff, wlp->wordp, 1);
		if(strcmp(firstletter, buff)){/* 先頭文字が変わった場合 */
			strncpy(firstletter, wlp->wordp,1);
			print_firstletter(firstletter[0]);
			memset(buff, '\0', BUFFSIZE);
		}
		/* 自分自身を表示 */
		print_word(wlp);

		/* 右の子ノードを表示 */ 
		display(wlp->rightp);
	}
}
/* 単語を出力する
*args 
* wlp 単語リストへのポインタ
*Return Value
* なし
*/
void print_word(wlist_t *wlp){
	int len;

	/* 単語フィールドを出力(スペースで調整) */
	
	printf("%s", wlp->wordp);	
	len = strlen(wlp->wordp);
	padding_space(WORDFIELDLENGTH - len);

	/* スペースフィールドを出力 */
	padding_space(SPACEFIELDLENGTH);
	/* ページフィールドを出力 */
	print_plist(wlp->top);
	printf("\n");
	
}

/* ページ番号を出力する
*args 
* plp ページリストへのポインタ
*Return Value
* なし
*/
void print_plist(plist_t *plp){

	int idx=0;

	char buff[256];

	char output[PAGEFIELDLENGTH];
	plist_t *thispage;

	memset(output, '\0', sizeof(output));


	for(thispage = plp; thispage != NULL; thispage = thispage->nextp){
		/* buffにページを格納する */
		/* 最後のページ以外は、カンマを付記する */
		(thispage->nextp != NULL)? sprintf(buff, "%d," , thispage->pnum): sprintf(buff, "%d", thispage->pnum);
		idx += strlen(buff);

		if(idx > PAGEFIELDLENGTH){/* ページフィールド長を超過する場合は、いったん出力してインデックスを元に戻す */
		
			/* ページ出力 */
			printf("%s\n", output);
			/* スペース調整 */
			padding_space(WORDFIELDLENGTH); padding_space(SPACEFIELDLENGTH);
			/* 初期化処理 */
			idx = 0;
			memset(output, '\0', sizeof(output));
			memset(buff, '\0', sizeof(buff));
		}
		strcat(output, buff);
	}
	if(0<strlen(output)){
		printf("%s\n",output);
	}
}
/* 指定された数だけスペースを出力する
*args 
* num スペースの数
*Return Value
* なし
*/
void padding_space(int num){
	int i;
	for(i=0; i<num; i++){
		printf(" ");
	}
}

